// gridgen.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

using namespace std;

typedef unsigned size_t;
typedef vector<size_t>    IntVector;
typedef vector<IntVector> IntMatrix;
typedef set<size_t>       IntSet;

class Grid
{
protected:
    IntSet rows_, columns_;
public:

    explicit Grid() {};
    ~Grid() {};

    size_t size() { return rows_.size()*columns_.size(); }

    IntSet& get_Rows() { return rows_; }
    IntSet& get_Columns() { return columns_; }

    void set_Rows(const IntSet& t)
    {
        IntSet::const_iterator iter;
        for (iter = t.begin(); iter != t.end(); ++iter)
            rows_.insert(*iter);
    }

    void set_Columns(const IntSet& t)
    {
        IntSet::const_iterator iter;
        for (iter = t.begin(); iter != t.end(); ++iter)
            columns_.insert(*iter);
    }

    void print()
    {
        IntSet::const_iterator iter;

        for (iter = rows_.begin(); iter != rows_.end(); ++iter)
            cout << (*iter)+1 << " ";
        cout << "0 "; 
        for (iter = columns_.begin(); iter != columns_.end(); ++iter)
            cout << (*iter)+1 << " ";
        cout << "0" << endl;
    }
};


bool operator <=(const IntSet& left, const IntSet& right)
{
    IntSet::const_iterator iter;

    if (left.size() > right.size()) 
        return false;

    for (iter = left.begin(); iter != left.end(); ++iter) // left \subset right ?
        if (right.find(*iter) == right.end()) 
            return false;

    return true; // left = right
}


bool operator <=(Grid& left, Grid& right)
{
    return (left.get_Rows() <= right.get_Rows()) && (left.get_Columns() <= right.get_Columns());
}


typedef vector<Grid> GridVector;


class GridsGenerator
{
protected:
    size_t     m_;
    size_t     n_;
    int        seed_;
    double     density_;
    bool       allow_dup_;
    IntMatrix  rel_;
    GridVector grids_;
    CRandomMersenne rnd_;

public:
    GridsGenerator(): rnd_(0)
    {}


    void add_Grid(Grid& g)
    {
        for (GridVector::iterator iter = grids_.begin(); iter != grids_.end(); ++iter)
            if (g <= (*iter))
            {
                //std::cout << "g <= (*iter)" << lf;
                return;
            }

            for (;;)
            {
                bool subsets_present = false;
                for (GridVector::iterator iter = grids_.begin(); iter != grids_.end(); ++iter)
                    if ((*iter) <= g)
                    {
                        //std::cout << "g >= (*iter)" << lf;
                        grids_.erase(iter);
                        subsets_present = true;
                        break;
                    }
                    if (!subsets_present)
                        break;
            }

            grids_.push_back(g);;
    }


    bool ones_Present(size_t j)
    {
        for (size_t i = 0; i < m_; ++i)
            if (rel_[i][j] == 1)
                return true;

        return false;
    }


    bool all_Ones(size_t i, IntSet& c)
    {
        IntSet::const_iterator iter;
        for (iter = c.begin(); iter != c.end(); ++iter)
            if (rel_[i][*iter] == 0)
                return false;

        return true;
    }


    bool duplicate_Rows(size_t i, size_t k)
    {
        for (size_t j = 0; j < n_; ++j)
            if (rel_[i][j] != rel_[k][j])
                return false;

        return true;
    }


    bool duplicate_Columns(size_t j, size_t k)
    {
        for (size_t i = 0; i < m_; ++i)
            if (rel_[i][j] != rel_[i][k])
                return false;

        return true;
    }


    bool duplicates_Present()
    {
        for (size_t i = 0; i < m_; ++i)
            for (size_t k = 0; k < m_; ++k)
                if (i != k)
                    if (duplicate_Rows(i, k))
                        return true;

        for (size_t j = 0; j < n_; ++j)
            for (size_t k = 0; k < n_; ++k)
                if (j != k)
                    if (duplicate_Columns(j, k))
                        return true;

        return false;
    }

    void find_Grids() 
    {
        grids_.reserve(m_*n_); 

        size_t nc = (1 << n_); // number of columns subsets

        for (size_t j = nc-1; j >= 1; --j) // non-empty columns subsets
        {
            Grid g;

            IntSet tr, tc;
            for (size_t k = 0; k < n_; ++k)
                if ((1<<k)&j)
                    tc.insert(k);

            for (size_t i = 0; i < m_; ++i)
                if (all_Ones(i, tc))
                    tr.insert(i);

            if (tr.size() != 0) 
            {
                g.set_Rows(tr);
                g.set_Columns(tc);
                add_Grid(g);
            }
        }
    }

    void generate_Relation()
    {
        for (size_t i = 0; i < m_; ++i)
            for (size_t j = 0; j < n_; ++j)
                if (rnd_.Random() < density_)
                    rel_[i][j] = 1;
                else
                    rel_[i][j] = 0;
    }

    void run(const char * fname)
    {
        CSimpleIniA ini;
        bool load_ok = (ini.LoadFile(fname) >= SI_OK);
        if (!load_ok) 
        {
            cout << "ini file error" << endl;
            return;
        }

        m_         = atoi(ini.GetValue("gridgen", "rows"));
        n_         = atoi(ini.GetValue("gridgen", "columns"));
        density_   = atof(ini.GetValue("gridgen", "ones_density"));
        seed_      = atoi(ini.GetValue("gridgen", "rand_seed"));
        allow_dup_ = atoi(ini.GetValue("gridgen", "allow_duplicates")) != 0;

        rnd_.RandomInit(seed_);

        rel_.resize(m_); 
        for (size_t i = 0; i < m_; ++i)
            rel_[i].resize(n_);

        generate_Relation();

        if (!allow_dup_)
            while (duplicates_Present())
                generate_Relation();

        find_Grids();
    }


    void print()
    {
        cout << "matrix " << m_ << " " << n_ << " " << density_ << " " << seed_ << " " << allow_dup_ << endl;
        for (size_t i = 0; i < m_; ++i)
        {
            for (size_t j = 0; j < n_; ++j)
                cout << rel_[i][j] << " ";
            cout << endl;
        }

        cout << "grids " << grids_.size() << endl;
        for (GridVector::iterator iter = grids_.begin(); iter != grids_.end(); ++iter)
            (*iter).print();
        cout << endl;

    }
};


int main(int argc, char* argv[])
{
    if (argc != 2)
    {
        cout << "usage: gridgen.exe file.ini" << endl;
        return 0;
    }

    GridsGenerator gg;
    gg.run(argv[1]);
    gg.print();

    return 0;
}

